package org.example.myleet.rosalind.tree;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        BufferedReader br = null;
        try {
            br = new BufferedReader(new FileReader(path));
            String line = br.readLine();
            int n = Integer.parseInt(line.trim());
            List<String> edgePairs = new ArrayList<>();
            while (null != (line = br.readLine()) && line.length() > 0) {
                edgePairs.add(line.trim());
            }
            solution.findMissedEdgeCount(n, edgePairs);
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (null != br) {
                try {
                    br.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    private UnionFindSet unionFindSet;

    public void findMissedEdgeCount(int n, List<String> edgePairArr) {
        unionFindSet = new UnionFindSet(n);
        for (String edgePair : edgePairArr) {
            String[] numbers = edgePair.split(" ");
            int num1 = Integer.parseInt(numbers[0]);
            int num2 = Integer.parseInt(numbers[1]);
            int parent = unionFindSet.query(num1);
            if (num1 == parent) {
                parent = unionFindSet.query(num2);
                if (num2 == parent) {
                    unionFindSet.union(num2, num1);
                } else {
                    unionFindSet.union(num1, parent);
                }
            } else {
                unionFindSet.union(num2, parent);
            }
        }
        Set<Integer> roots = new HashSet<>(unionFindSet.nodeParent.values().size());
        for (int key : unionFindSet.nodeParent.keySet()) {
            roots.add(unionFindSet.query(key));
        }
        System.out.println(roots.size() - 1);
    }

    static class UnionFindSet {
        Map<Integer, Integer> nodeParent;

        public UnionFindSet(int n) {
            nodeParent = new HashMap<>(n);
            for (int i = 1; i <= n; ++i) {
                nodeParent.put(i, i);
            }
        }

        public int query(int node) {
            int parent = nodeParent.get(node);
            if (node == parent) {
                return parent;
            }
            parent = query(parent);
            nodeParent.put(node, parent);
            return parent;
        }

        public void union(int x, int y) {
            int parentX = query(x);
            int parentY = query(y);
            nodeParent.put(parentX, parentY);
        }
    }
}
